package com.example.demo.leetcode.zuocheng.sort;

import java.util.Arrays;

/**
 * @author xujm
 * @version V2.4
 * 基数排序
 * 适合场景: 量比较大， 但是数据范围不大
 *
 * @since 2.4.0 2021/7/24 14:27
 */
public class Arr_基数排序 {

    public static void main(String[] args) {

        int [] arr={522,521,334,567,235,21,21};
        int maxLen = getMaxLen(arr);
        int [] res = sort(arr,maxLen);
        for(int i =0;i<res.length;i++){
            System.out.println(res[i]);
        }
    }

    //    27  34  52
    //    52  34  27

    public static int getMaxLen(int [] arr){

        int max = 0;
        for(int i =0 ;i<arr.length;i++){
            max = Math.max(max,arr[i]);
        }
        return String.valueOf(max).length();
    }

    public static int [] sort(int [] arr, int len){

        int [] result = new int[arr.length];
        int [] count = new int[10];

        for(int i=0;i<len;i++){
            int devision = (int)Math.pow(10,i); // 10的i次方
            for(int j=0;j<arr.length;j++){
                int num = arr[j]/devision % 10; // 获取 个位/十位/百位
                count[num]++;
            }

            // 累加数组
            // 假设原数组 arr 是   2,2,3,4,5
            // 那么 count 数组 现在是    值  0  0  2   1  1  1
            //                         下标 0  1  2   3  4  5
            // 那么 count的累加数组是 值  0  0  2   3  4  5
            //                      下标 0  1  2   3  4  5
            // 此时 count累加数组的值 可以看做result结果数组的 (下标+1)
            // count 累加数组的 下标 则是 目标值的对应位数(个位/十位/百位)

            //个数累加以后，值 转换成结果数组result的下标
            for(int m=1;m<count.length;m++){
                count[m] = count[m] + count[m-1];
            }


            //从后往前遍历，因为大的数要先遍历到，拿下标比较大的。
            for(int n =arr.length-1;n>=0;n--){
                int num = arr[n]/devision%10;  //拿到 个位/十位  对应是count累加数组的下标
                result[--count[num]] = arr[n]; // count累加数组的值-1  恰好是result中的位置
            }

            //result 复制给 arr, 个位排序处理结束，开始十位排序处理
            System.arraycopy(result,0,arr,0,arr.length);
            Arrays.fill(count,0);
        }
        return result;
    }



}
